1594. Закодированная сумма

Имеется набор строк, каждая из которых представляет собой натуральное число. Только вместо цифр строки содержат буквы от ‘A’ до ‘J’. Каждая буква обозначает одну цифру, а каждая цифра кодируется только одной буквой. Ни одно число не начинается нулем. В задаче требуется найти наибольшее возможное значение суммы всех чисел.

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество строк n (1 ≤ n ≤ 50). Далее следуют n строк, содержащие буквы от ‘A’ до ‘J’.

Выход. Для каждого теста в отдельной строке вывести наибольшее возможное значение суммы всех чисел.

Пример входа	Пример выхода
2 ABC BCA 1 ABCDEFGHIJ	1875 9876543210

РЕШЕНИЕ

жадный алгоритм

Анализ алгоритма

Элементы массива numbers содержат 10 допустимых букв: от ‘A’ до ‘J’. Запишем каждое число в десятичной системе счисления и просуммируем коэффициенты при одинаковых буквах. Например, для первого теста ABC = 100*A + 10*B + C, BCA = 100*B + 10*C + A. Сумма коэффициентов при букве ‘A’ равна 101, при ‘B’ – 110, при ‘C’ – 11. Массив m содержит эти данные в виде пар: <коэффициент, буква>.

Поскольку нам следует максимизировать полученную сумму, то букве с наибольшим коэффициентом должна соответствовать наибольшая цифра, то есть 9. Следующему по величине коэффициенту – цифра 8 и так далее. Сортируем элементы массива m по возрастанию коэффициентов. Единственная проблема – если в сумме задействованы все десять цифр (включая ноль), то не всякая буква может принимать значение 0, а только та, которая не встречается первой в словах. В массиве canzero отмечаем буквы, которые могут принимать нулевое значение: canzero[i] = 1, если буква ‘A’ + i может принимать значение 0.

В отсортированном по значениям коэффициентов массиве m ищем первую букву, которая может принимать нулевое значение и переставляем ее на нулевую позицию. Если в сумме задействовано менее 10 букв, но никакая буква нулевого значения принимать не будет. Сортируем ячейки массива m от первой до девятой.

После описанных процедур букве m[i].first приписываем значение i и вычисляем максимально возможное значение искомой суммы, равное

Реализация алгоритма

Объявим глобальные переменные.

vector<pair<long long,char> > m(10);

vector<string> numbers;

int canzero[10];

long long maximumSum(void)

{

int i, j;

long long pow10, s;

for(i = 0; i < 10; i++)

m[i].first = 0, m[i].second = i + 'A',canzero[i] = 1;

for(i = 0; i < numbers.size(); i++)

{

pow10 = 1;

for(j = numbers[i].size() - 1; j >= 0; j--)

{

m[numbers[i][j]-'A'].first += pow10;

pow10 *= 10;

}

canzero[numbers[i][0]-'A'] = 0;

}

sort(m.begin(),m.end());

for(i = 0; !canzero[m[i].second - 'A']; i++);

swap(m[0],m[i]);

sort(m.begin() + 1,m.end());

for(s = i = 0; i < 10; i++)

s += m[i].first * i;

return s;

}

Основная часть программы.

while(scanf("%d\n",&n) == 1)

{

numbers.clear();

for(i = 0; i < n; i++)

gets(s), numbers.push_back(s);

res = maximumSum();

printf("%lld\n",res);

}